// @FileName  :h7t2.c
// @Time      :2024/5/24 14:13
// @Author    :YKW
//# include <bits/stdc++.h>
//using namespace std;
# include <stdio.h>
# include <stdlib.h>
# include <math.h>
# include <string.h>
# include <stdlib.h>

#define N 1009
struct edge {
    int nex, id;
} G[N][N]; //邻接表
//点 边 。 。 。 每个点的度 1 当前记录的路线 是否经过某边 是否经过某点
int n, m, u, v, e, deg[N], ans[N], visEdge[N], visPoint[N];

int cmp(const void *a, const void *b) {
    return ((struct edge *) a)->id - ((struct edge *) b)->id;
}

void dfs(int point, int depth) {
    if (point == n - 1) {
        for (int i = 0; i < depth; i++)
            printf("%d ", ans[i]);
        printf("\n");
//        return;
    }
    for (int i = 0; i < deg[point]; i++) {
        if (visPoint[G[point][i].nex] == 0 && visEdge[G[point][i].id] == 0) {
            ans[depth] = G[point][i].id;
            visPoint[G[point][i].nex] = 1;
            visEdge[G[point][i].id] = 1;
            dfs(G[point][i].nex, depth + 1);
            visPoint[G[point][i].nex] = 0;
            visEdge[G[point][i].id] = 0;
        }
    }
}

int main() {
    setbuf(stdout, NULL);
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &e, &u, &v);
        G[u][deg[u]].nex = v;
        G[u][deg[u]].id = e;
        deg[u]++;
        G[v][deg[v]].nex = u;
        G[v][deg[v]].id = e;
        deg[v]++;
    }
    for (int i = 0; i < n; i++)
        qsort(G[i], deg[i], sizeof(struct edge), cmp);
    visPoint[0] = 1;
    dfs(0, 0);
    return 0;
}
/*
6 8
1 0 1
2 1 2
3 2 3
4 2 4
5 3 5
6 4 5
7 0 5
8 0 1
 */